package leetcode.hot100;

/**
 * Created on 2021-01-22 。
 *
 * @author wll 1978992154@qq.com
 */

import common.ListNode;
import utils.MyUtil;

/**
 * 反转一个链表
 */
public class ReverseLinkList {

    /**
     * 使用双指针反转一个链表
     * @param head 头指针
     * @return 反转后的头指针
     */
    public static ListNode reverseListNodeWithTwoPoint(ListNode head){
        ListNode pre = null,cur = head;
        while (cur != null){
            // 先记录一下cur的下一个节点
            ListNode tempNext = cur.next;
            // 反转指向
            cur.next = pre;
            // 两个指针同时后移动
            pre = cur;
            cur = tempNext;
        }
        return pre;
    }

    /**
     * 翻转链表使用递归的方式
     * @param head 头结点
     * @return 反转后的头指针
     */
    public ListNode reversListNodeWithRecursion(ListNode head){
        if (head ==null || head.next == null){
            return head;
        }
        ListNode ret = reversListNodeWithRecursion(head.next);
        head.next.next = head;
        head.next = null;
        return ret;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(4);
        MyUtil.displayListNode(head);
        ListNode t = reverseListNodeWithTwoPoint(head);
        MyUtil.displayListNode(t);
    }
}
